package pers.qianyu.month_202012.date_20201210;

import org.junit.*;

import java.util.*;

/**
 * 37. 解数独
 * https://leetcode-cn.com/problems/sudoku-solver/
 *
 * @author mizzle rain
 * @date 2020-12-10 21:26
 */
public class SolveSudoku {
    public void solveSudoku(char[][] board) {
        int count = 0;
        for (char[] chars : board) {
            for (char aChar : chars) {
                if (aChar == '.') {
                    count++;
                }
            }
        }
        int[][] loc = new int[count][2];
        int p1 = 0;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == '.') {
                    loc[p1++] = new int[]{i, j};
                }
            }
        }
        recur(board, loc, count, 0);
    }

    private boolean recur(char[][] board, int[][] loc, int count, int index) {
        if (index == count) {
            return true;
        }
        for (int num = 1; num < 10; num++) {
            if (isInvalid(board, num, loc[index])) {
                continue;
            }
            board[loc[index][0]][loc[index][1]] = (char) ('0' + num);
            if (recur(board, loc, count, index + 1)) {
                return true;
            }
            board[loc[index][0]][loc[index][1]] = '.';
        }
        return false;
    }

    private boolean isInvalid(char[][] board, int num, int[] loc) {
        int row = loc[0], col = loc[1];
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == num + '0') {
                return true;
            }
            if (board[i][col] == num + '0') {
                return true;
            }
            // 非常巧妙地一种方法用来 判断周围 3 * 3 方格内有无重复的数字
            if (board[(row / 3) * 3 + i / 3][(col / 3) * 3 + i % 3] == num + '0') {
                return true;
            }
        }
        /*
        // 下面是比较麻烦的一种判断 周围 3 * 3 方格内有无重复的方法
        int[][] arr = {
                {1, 2, 1, 2},
                {1, 2, 3, 5},
                {1, 2, 6, 8},
                {3, 5, 1, 2},
                {3, 5, 3, 5},
                {3, 5, 6, 8},
                {6, 8, 1, 2},
                {6, 8, 3, 5},
                {6, 8, 6, 8}
        };
        for (int[] ints : arr) {
            if (row >= ints[0] && row <= ints[1] && col >= ints[2] && col <= ints[3]) {
                for (int i = ints[0]; i <= ints[1]; i++) {
                    for (int j = ints[2]; j <= ints[3]; j++) {
                        if (board[i][j] == num + '0') {
                            return true;
                        }
                    }
                }
            }
        }*/
        return false;
    }

    @Test
    public void test1() {
        char[][] board = new char[][]{
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
        };
        new SolveSudoku().solveSudoku(board);
        Arrays.stream(board).forEach(item -> System.out.println(Arrays.toString(item)));
    }

    @Test
    public void test12() {
        System.out.println(1 / 3);
        System.out.println(1 % 3);
    }
}
